home
***
CD-ROM
|
disk
|
FTP
|
other
***
search
/
Language/OS - Multiplatform Resource Library
/
LANGUAGE OS.iso
/
smaltalk
/
gnu_st.lha
/
gnu_st
/
smalltalk-1.1.1
/
IdentityDictionary.st
< prev
next >
Wrap
Text File
|
1991-09-12
|
8KB
|
297 lines
"======================================================================
|
| IdentityDictionary Method Definitions
|
======================================================================"
"======================================================================
|
| Copyright (C) 1990, 1991 Free Software Foundation, Inc.
| Written by Steve Byrne.
|
| This file is part of GNU Smalltalk.
|
| GNU Smalltalk is free software; you can redistribute it and/or modify it
| under the terms of the GNU General Public License as published by the Free
| Software Foundation; either version 1, or (at your option) any later version.
|
| GNU Smalltalk is distributed in the hope that it will be useful, but WITHOUT
| ANY WARRANTY; without even the implied warranty of MERCHANTABILITY or FITNESS
| FOR A PARTICULAR PURPOSE. See the GNU General Public License for more
| details.
|
| You should have received a copy of the GNU General Public License along with
| GNU Smalltalk; see the file COPYING. If not, write to the Free Software
| Foundation, 675 Mass Ave, Cambridge, MA 02139, USA.
|
======================================================================"
"
| Change Log
| ============================================================================
| Author Date Change
| sbyrne 25 Apr 89 created.
|
"
Dictionary variableSubclass: #IdentityDictionary
instanceVariableNames: 'values'
classVariableNames: ''
poolDictionaries: ''
category: nil.
IdentityDictionary comment:
'I am similar to dictionary, except that my representation is
different, and I use the object identity comparision message == to
determine equivalence of indices.' !
!IdentityDictionary class methodsFor: 'instance creation'!
new
^self new: 4
!
new: anInteger
^(super new: anInteger) initValues
!!
!IdentityDictionary methodsFor: 'accessing'!
add: anAssociation
self at: anAssociation key put: anAssociation value.
^anAssociation
!
at: key put: value
| index |
index _ self findKeyIndex: key.
(self basicAt: index) isNil
ifTrue: [ tally _ tally + 1 ].
self basicAt: index put: key.
values basicAt: index put: value.
^value
!
at: key ifAbsent: aBlock
| index |
index _ self findKeyIndex: key.
(self basicAt: index) isNil
ifTrue: [ ^aBlock value ].
^values basicAt: index
!
associationAt: key ifAbsent: aBlock
| index assoc|
^Association key: key
value: (self at: key
ifAbsent: [ ^aBlock value ])
!
keyAtValue: value ifAbsent: exceptionBlock
self indicesDo:
[ :i | value = (values basicAt: i)
ifTrue: [ ^self basicAt: i] ].
^exceptionBlock value
!!
!IdentityDictionary methodsFor: 'dictionary testing'!
includesAssociation: anAssociation
| index |
index _ self findKeyIndex: anAssociation key.
^(self basicAt: index) notNil
and: [ (values basicAt: index) = anAssociation value ]
!
includesKey: key
^(self basicAt: (self findKeyIndex: key)) notNil
!!
!IdentityDictionary methodsFor: 'dictionary removing'!
removeKey: key ifAbsent: aBlock
| index value|
index _ self findKeyIndexNoGrow: key ifAbsent: [ ^aBlock value ].
value _ values basicAt: index.
self basicAt: index put: nil.
values basicAt: index put: nil.
tally _ tally - 1.
self rehashObjectsAfter: index.
^ value
!!
!IdentityDictionary methodsFor: 'dictionary enumerating'!
associationsDo: aBlock
self indicesDo:
[ :i | aBlock value: (Association key: (self basicAt: i)
value: (values basicAt: i)) ]
!
"These could be implemented more efficiently by
doing the explicit scanning of the dictionary by hand"
keysDo: aBlock
self indicesDo: [ :i | aBlock value: (self basicAt: i) ]
!
do: aBlock
self indicesDo: [ :i | aBlock value: (values basicAt: i) ]
!
select: aBlock
| newDict |
newDict _ self species new.
self indicesDo:
[ :i | (aBlock value: (values basicAt: i))
ifTrue: [ newDict add: (Association key: (self basicAt: i)
value: (values basicAt: i))] ].
^newDict
!!
!IdentityDictionary methodsFor: 'misc math methods'!
= aDictionary
tally ~= aDictionary size ifTrue: [ ^false ].
self indicesDo:
[ :i | (values basicAt: i) = (aDictionary at: (self basicAt: i)
ifAbsent: [ ^false ])
ifFalse: [ ^false ] ].
^true
!
hash
| hashValue |
hashValue _ tally.
self indicesDo:
[ :i | hashValue _ hashValue + (self basicAt: i) hash.
hashValue _ hashValue + (values basicAt: i) hash ].
^hashValue
!!
!IdentityDictionary methodsFor: 'printing'!
printOn: aStream
aStream nextPutAll: self class name , ' (' .
aStream nl.
self indicesDo:
[ :i | aStream tab.
(self basicAt: i) storeOn: aStream.
aStream nextPut: $,.
(values basicAt: i) storeOn: aStream.
aStream nl ].
aStream nextPut: $)
!!
!IdentityDictionary methodsFor: 'storing'!
storeOn: aStream
| hasElements |
aStream nextPutAll: '(', self class name , ' new'.
hasElements _ false.
self indicesDo:
[ :i | aStream nextPutAll: ' at: '.
(self basicAt: i) storeOn: aStream.
aStream nextPutAll: ' put: '.
(values basicAt: i) storeOn: aStream.
aStream nextPut: $;.
hasElements _ true ].
hasElements ifTrue: [ aStream nextPutAll: ' yourself' ].
aStream nextPut: $)
!!
!IdentityDictionary methodsFor: 'private methods'!
initValues
values _ Array new: self basicSize
!
indicesDo: aBlock
"Invokes aBlock with all the indices of the set that have valid keys"
1 to: self basicSize do:
[ :i | (self basicAt: i) notNil
ifTrue: [ aBlock value: i ] ]
!
rehashObjectsAfter: index
"### rehash bug needs to be fixed!!!!"
"Rehashes all the objects in the collection after index to see if any of
them hash to index. If so, that object is copied to index, and the
process repeats with that object's index, until a nil is encountered."
| i size count key |
i _ index.
size _ self basicSize.
count _ size.
[ count > 0 ]
whileTrue:
[ i _ i \\ size + 1.
key _ self basicAt: i.
key isNil ifTrue: [ ^self ].
((key hash \\ size) + 1) = index
ifTrue: [ self basicAt: index put: key.
values basicAt: index put: (values basicAt: i).
self basicAt: i put: nil. "Be tidy"
values basicAt: i put: nil."Be tidy"
index _ i ].
count _ count - 1 ]
!
findKeyIndex: aKey ifFull: aBlock
"Tries to see if aKey exists as the key of an indexed variable (which is an
association). If it's searched the entire dictionary and the key is
not to be found, aBlock is evaluated and it's value is returned."
| index count size key |
size _ self basicSize.
index _ aKey hash \\ size + 1.
count _ size.
[ count > 0 ]
whileTrue:
[ key _ self basicAt: index.
(key isNil or: [ key == aKey ])
ifTrue: [ ^index ].
index _ index \\ size + 1.
count _ count - 1. ].
^aBlock value
!
findKeyIndex: aKey
"Finds an association with the given key in the dictionary and returns its
index. If the dictionary doesn't contain the object and there is no nil
element, the dictionary is grown and then the index of where the object
would go is returned."
^self findKeyIndex: aKey
ifFull: [ self grow.
self findKeyIndexNoGrow: aKey
ifAbsent: [ ^self error: 'failed to grow a new empty element!!!' ] ]
!
grow
| newDict |
newDict _ self species new: self basicSize + self growSize.
self indicesDo: [ :i | newDict at: (self basicAt: i)
put: (values basicAt: i) ].
^self become: newDict
!
growSize
^32
!!